
// 快速排序、快速排序优化：三数取中、三路划分、小区间使用直接插入排序、使用仿函数实现升降序自由切换
// 希尔排序、选择排序、堆排序、冒泡排序、计数排序、归并排序
// 寻找旋转数组的最小值
#include <iostream>
#include <vector>
#include <algorithm>

// honor版本
int PartSort1(std::vector<int> &num, int left, int right)
{
    if (right < left)
        throw std::exception();

    int keyi = left;
    int key = num[left];
    while (left < right)
    {
        // 右边找一个小的
        while (left < right && num[right] >= key)
            right--;
        // 左边找一个大的
        while (left < right && num[left] <= key)
            left++;

        std::swap(num[left], num[right]);
    }
    std::swap(num[left], num[keyi]);
    return left;
}

void QuickSort(std::vector<int> &num, int left, int right)
{
    if (left == right)
        return;
    // 排序
    int index = PartSort1(num, left, right);
    // 左区间
    if (index > left)
        QuickSort(num, left, index - 1);
    // 右区间
    if (index < right)
        QuickSort(num, index + 1, right);
}

// 仿函数
// 升序
template <class T>
struct Less
{
    bool operator()(const T &t1, const T &t2) const
    {
        return t1 < t2 ? true : false;
    }
};

// 降序
template <class T>
struct Greater
{
    bool operator()(const T &t1, const T &t2) const
    {
        return t1 > t2 ? true : false;
    }
};

// 三数取中
int GetKeyIndex(std::vector<int> &num, int left, int right)
{
    int middle = (right - left) / 2 + left;

    int left_num = num[left];
    int right_num = num[right];
    int middle_num = num[middle];

    if (left_num < right_num)
    {
        if (middle_num <= left_num)
            return left;
        else
        {
            if (middle_num <= right_num)
                return middle;
            else
                return right;
        }
    }
    // left_num > right_num
    else
    {
        if (right_num >= middle_num)
            return right;
        else
        {
            if (left_num >= middle_num)
                return middle;
            else
                return left;
        }
    }
}

// 直接插入排序
template <typename Compare>
void InsertSort(std::vector<int> &num, int left, int right, Compare compare)
{
    if (right < left)
        throw std::exception();

    for (int i = left; i <= right; i++)
    {
        int key = num[i];
        int end = i - 1;
        while (end >= 0)
        {
            if (compare(key, num[end]))
            {
                num[end + 1] = num[end];
                end--;
            }
            else
            {
                break;
            }
        }
        num[end + 1] = key;
    }
}

// 三路划分 + 三数取中 + 小于10个数据的插入排序
template <typename Compare>
std::vector<int> PartSort2(std::vector<int> &num, int left, int right, Compare compare)
{
    if (right < left)
        throw std::exception();

    if (right - left <= 10)
    {
        // 直接插入排序
        std::cout << "直接插入排序" << std::endl;
        InsertSort(num, left, right, compare);
    }
    // 三数取中
    int keyi = GetKeyIndex(num, left, right);
    std::swap(num[left], num[keyi]);
    std::cout << "key：" << num[left] << std::endl;

    // 三路划分
    int cur = left + 1;
    while (cur <= right)
    {
        if (compare(num[cur], num[left]))
            std::swap(num[left++], num[cur++]);
        else if (compare(num[left], num[cur]))
            std::swap(num[right--], num[cur]);
        else
            cur++;
    }
    return {left, right};
}

template <typename Compare>
void QuickSortMax(std::vector<int> &num, int start, int end, Compare compare)
{
    if (start == end)
        return;

    // 排序
    std::vector<int> index = PartSort2(num, start, end, compare);
    int left = index[0];
    int right = index[1];

    // 左区间
    if (left > start)
        QuickSortMax(num, start, left - 1, compare);
    // 右区间
    if (right < end)
        QuickSortMax(num, right + 1, end, compare);
}
void QuickSortMax(std::vector<int> &num, int start, int end)
{
    QuickSortMax(num, 0, num.size() - 1, Less<int>());
}

// 希尔排序
// const引用可以延长临时对象的生命周期，因为延长的内容只会被访问读取，不会修改产生安全问题
// 同时大量的临时对象被延长生命周期也会占用内存空间
template <typename Compare>
void ShellSort(std::vector<int> &num, const Compare &compare)
{
    if (num.size() == 0)
        return;

    int gap = num.size();
    while (gap > 1)
    {
        gap = gap / 2;
        for (int i = 0; i < num.size(); i += gap)
        {
            int key = num[i];
            int end = i - gap;
            while (end >= 0)
            {
                if (compare(key, num[end]))
                {
                    num[end + gap] = num[end];
                    end -= gap;
                }
                else
                    break;
            }
            num[end + gap] = key;
        }
    }
}

void ShellSort(std::vector<int> &num)
{
    ShellSort(num, Less<int>());
}

// 选择排序
void SelectSort(std::vector<int> &num)
{
    if (num.size() == 0)
        return;

    int left = 0, right = num.size() - 1;
    while (left < right)
    {
        int mini = left, maxi = left;

        for (int i = left; i <= right; i++)
        {
            // 找最大
            if (num[i] > num[maxi])
                maxi = i;
            // 找出最小
            if (num[i] < num[mini])
                mini = i;
        }
        std::swap(num[left], num[mini]);
        if (left == maxi)
            std::swap(maxi, mini);
        std::swap(num[right], num[maxi]);

        left++;
        right--;
    }
}

// 冒泡排序
void BubbleSort(std::vector<int> &num)
{
    if (num.size() <= 1)
        return;

    size_t length = num.size();

    for (int i = 0; i < length - 1; i++)
    {
        for (int j = 0; j < length - 1 - i; j++)
        {
            if (num[j] > num[j + 1])
                std::swap(num[j], num[j + 1]);
        }
    }
}

// 计数排序
void CountSort(std::vector<int> &num)
{
    if (num.size() <= 1)
        return;

    // 遍历一遍，计算出数据范围
    int min = INT32_MAX;
    int max = 0;
    for (int i = 0; i < num.size(); i++)
    {
        if (num[i] < min)
            min = num[i];
        else if (num[i] > max)
            max = num[i];
    }
    int range = max - min + 1;

    // 开辟空间
    std::vector<int> tmp;
    tmp.resize(range, 0);

    // 开始计数
    for (int i = 0; i < num.size(); i++)
    {
        tmp[num[i] - min]++;
    }

    // 计算每个元素在整个数组中有几个大于等于他的
    for (int i = 1; i < range; i++)
    {
        tmp[i] += tmp[i - 1];
    }

    std::vector<int> ret;
    ret.resize(num.size(), 0);

    for (int i = num.size() - 1; i >= 0; i--)
    {
        ret[tmp[num[i] - min] - 1] = num[i];
        tmp[num[i] - min]--;
    }
    num.swap(ret);
}

// 堆排序
//  void HeapSort(std::vector<int> &num)
//  {
//      if(num.size() <= 1)
//          return;

//     //建堆
//     std::make_heap(num.begin(), num.end());

//     for(int i = 0; i < num.size(); i++)
//     {
//         pop_heap(num.begin(), num.end() - i);
//     }
// }

// 向下调整法
void AdjustDown(std::vector<int> &num, int parent, int size)
{
    int child = parent * 2 + 1;
    while (child < size)
    {
        // 找出孩子中最大的
        if (child + 1 < size && num[child] < num[child + 1])
        {
            child = child + 1;
        }
        // 调整
        if (num[parent] >= num[child])
            break;
        std::swap(num[parent], num[child]);
        // 更新下标
        parent = child;
        child = parent * 2 + 1;
    }
}

// 堆排序--大堆
void HeapSort(std::vector<int> &num)
{
    // 建堆
    // 倒数第一个非叶子节点下标：（n-1-1）/2
    for (int i = (num.size() - 2) / 2; i >= 0; i--)
    {
        AdjustDown(num, i, num.size());
    }

    // 排序
    int end = num.size() - 1;
    while (end > 0)
    {
        std::swap(num[0], num[end]);
        AdjustDown(num, 0, end);
        end--;
    }
}

// 归并排序
void Merge(std::vector<int> &num, int start, int end, int middle, std::vector<int> &tmp)
{
    int i = start, j = middle + 1, index = start;
    // 合并两个区间数组
    while (i <= middle && j <= end)
    {
        if (num[i] <= num[j])
            tmp[index++] = num[i++];
        else
            tmp[index++] = num[j++];
    }
    while (i <= middle)
        tmp[index++] = num[i++];
    while (j <= end)
        tmp[index++] = num[j++];

    for (int i = start; i <= end; i++)
        num[i] = tmp[i];
}

// 确定区间
void MergeSort(std::vector<int> &num, int start, int end, std::vector<int> &tmp)
{
    if (start >= end)
        return;

    int middle = (end - start) / 2 + start; // 中间下标
    MergeSort(num, start, middle, tmp);
    MergeSort(num, middle + 1, end, tmp);
    Merge(num, start, end, middle, tmp);
}

// 二分查找
int BinarySerach(const std::vector<int> &num, int number)
{
    if (num.size() == 0)
        return -1;

    int left = 0, right = num.size() - 1;
    while (left <= right)
    {
        int middle = left + ((right - left) >> 1);
        if (num[middle] < number)
            left = middle + 1;
        else if (num[middle] > number)
            right = middle - 1;
        else
            return middle;
    }
    return -1;
}

void TestSort()
{
    std::vector<int> num = {5, 3, 2, 5, 6, 8, 7, 10, 4, 2, 4, 5, 7, 3, 6, 8, 4, 2, 1};
        // std::vector<int> num = {2,3,4,1,2,7};
        // QuickSortMax(num, 0, num.size() - 1, Greater<int>());
        // ShellSort(num);
        // SelectSort(num);
        // BubbleSort(num);
        CountSort(num);
        // HeapSort(num);

        // std::vector<int> tmp;
        // tmp.reserve(num.size());
        // MergeSort(num, 0, num.size() - 1, tmp);

        for (auto &n : num) {
            std::cout << n << " ";
        } std::cout
        << std::endl;

        // std::cout << BinarySerach(num, 2) << std::endl;
        // std::cout << BinarySerach(num, 100) << std::endl;
        // std::cout << BinarySerach(num, 3) << std::endl;
        // std::cout << BinarySerach(num, 1) << std::endl;
}

//找旋转数组最小值
int MinInOrder(std::vector<int>& num, int left, int right)
{
    std::cout << left << " " << right << std::endl;
    int ret = num[left];
    for(int i = left + 1; i <= right; i++)
    {
        ret = ret < num[i] ? ret : num[i];
        std::cout << ret << std::endl;
    }
    return ret;
}


int Min(std::vector<int> &num)
{
    if(num.size() == 0)
        throw std::exception();

    int left = 0, right = num.size() - 1, index = 0;
    while(num[left] >= num[right])
    {
        if(right - left == 1)
        {
            index = right;
            break;
        }
        int middle = left + ((right - left) >> 1);
        //如果说三个位置的数相等时，就只能用遍历判断了,但可能是二分查找了之后，舍弃了一大部分范围下的遍历
        if(num[middle] == num[left] && num[middle] == num[right])
            return MinInOrder(num, left, right);
        if(num[middle] >= num[left])
            left = middle;
        else if(num[middle] <= num[right])
            right = middle;
    }
    return num[index];
}

int main()
{
    // TestSort()
    // std::vector<int> num = {3,4,5,1,2};
    // std::vector<int> num = {1,0,1,1,1};
    // std::vector<int> num = {2,2,2,2,2,1,2};
    std::vector<int> num = {0};
    std::cout << Min(num) << std::endl;
    num = {0,1,2,3,4};
    std::cout << Min(num) << std::endl;
    
    return 0;
}
